package xyz.xiaotugou.dataStructure.basic;

import org.w3c.dom.Node;

import java.util.Collection;

/**
 * @author ysy
 * @version 1.0
 * @Title: 自定义链表
 *      LinkedList extends AbstractSequentialList implements List, Deque
 *          - 算法时间复杂度：
 *                  - prepend头查：O(1)
 *                  - append尾插：O(1)
 *                  - lookup随机查询：O(n)
 *                  - insert随机插入：O(1)
 *                  - delete删除：O(1)
 *          - 应用场景：LRU缓存算法
 *          https://www.jianshu.com/p/b1ab4a170c3c
 *          https://leetcode-cn.com/problems/lru-cache
 *
 * @Note <b>ProjectName:</b> Pre-research
 * <br><b>PackageName:</b> xyz.xiaotugou.dataStructure.basic
 * <br><b>ClassName:</b> MyLinkedList1
 * <br><b>Date:</b> 2022/1/5 22:23
 */
public class MyLinkedList1<T> {

    /**
     * 头节点指针
     **/
    private Node<T> first;

    /**
     * 尾节点指针
     **/
    private Node<T> last;

    /**
     * 链表实际长度
     **/
    private int size;

    public MyLinkedList1() {

    }
    public MyLinkedList1(Collection<? extends T> collection) {
        this();
        addAll(collection);

    }

    /**
     * 链表节点
     */
    public static class Node<T> {
        /**
         * 数据
         **/
        T data;
        /**
         * 下一个节点
         **/
        MyLinkedList1.Node<T> next;
        /**
         * 上一个节点
         **/
        MyLinkedList1.Node<T> prev;

        Node(T data) {
            this.data = data;
        }
        Node(Node<T> prev, T data, Node<T> next) {
            this.prev = prev;
            this.data = data;
            this.next = next;
        }
    }

    /**
     * @Author ysy
     * @Description 根据索引获取节点对象
     * @Date 2022/1/10 13:04
     * @Param 
     * @return xyz.xiaotugou.dataStructure.basic.MyLinkedList1.Node<T>
     **/
    Node<T> node(int index){
        Node<T> x;
        // 若index小于1/2的size，从前往后遍历
        if(index < (size >> 1)){
            x = first;
            for(int i = 0; i < index; i++){
                x = x.next;
            }
        } else {
            // 若index大于1/2的size，从后往前遍历
            x = last;
            for(int i = size-1; i > index; i--){
                x = x.next;
            }
        }
        return x;
    }

    /**
     * @Author ysy
     * @Description 尾插
     * @Date 2022/1/5 22:33
     * @Param data 待插入的值
     * @return void
     **/
    public void add(T data){
        final Node<T> oldLast = last;
        // 初始化新的last节点
        Node<T> newLast = new Node<>(oldLast, data, null);
        last = newLast;
        // 如果原对象为空，初始化头节点值
        if(oldLast == null){
            first = newLast;
        } else {
            // 如果原对象不为空，为之前的尾节点指定next
            oldLast.next = newLast;
        }
    }

    /**
     * @Author ysy
     * @Description 指定位置，插入值
     * @Date 2022/1/5 22:30
     * @Param data 待插入的值
     * @param index 插入的位置(0开始)
     * @return void
     **/
    public void add(int index, T data){
        checkIndex(index);
        if(index == size){
            add(data);
        } else {
            linkBefore(data, node(index));
        }
    }

    /**
     * @Author ysy
     * @Description 在指定节点的前面插入数据
     * @Date 2022/1/10 13:07
     * @Param 
     * @return void
     **/
    private void linkBefore(T data, Node<T> node) {
        final Node<T> preNode = node.prev;
        // 初始化新节点，指定prev、next
        final Node<T> newNode = new Node<>(preNode, data, node);
        // 为原节点指定prev
        node.prev = newNode;
        // 若原节点的first节点，进行first重置
        if(preNode == null){
            first = newNode;
        }else {
            // 若不是，则将原prev节点link至当前节点
            preNode.next = newNode;
        }
        size ++;
    }

    /**
     * @Author ysy
     * @Description 校验索引有效性
     * @Date 2022/1/10 12:59
     * @Param 
     * @return void
     **/
    private void checkIndex(int index) {
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: " + size);
        }
    }

    /**
     * @Author ysy
     * @Description 修改值 【O(1)】
     * @Date 2022/1/5 22:33
     * @Param data 待修改的值
     * @return void
     **/
    public T set(int index, T data){
        checkIndex(index);
        // 获取原位置的节点
        Node<T> node = node(index);
        T oldValue = node.data;
        // 重新赋值
        node.data = data;
        return oldValue;
    }

    /**
     * @Author ysy
     * @Description 查询值
     * @Date 2022/1/10 13:15
     * @Param 
     * @return T
     **/
    public T get(int index) {
        checkIndex(index);
        return node(index).data;
    }

    /**
     * @Author ysy
     * @Description 获取指定位置的值
     * @Date 2022/1/5 22:33
     * @Param data 待查询的值
     * @return 查询到的结果
     **/
    public int indexOf(T data){
        int index = 0;
        // 如果数据为null，使用==比较
        if(data == null){
            // 遍历链表比较
            for (Node<T> node = first; node != null; node = node.next){
                if(node.data == null){
                    return index;
                } else {
                    index++;
                }
            }
        } else {
            // 如果数据不为null，使用equals比较
            for (Node<T> node = first; node != null; node = node.next){
                if(data.equals(node.data)){
                    return index;
                } else {
                    index++;
                }
            }
        }
        return -1;
    }



    /**
     * @Author ysy
     * @Description 删除指定位置的值
     * @Date 2022/1/5 22:33
     * @Param index 索引
     * @return void
     **/
    public void remove(int index){
        checkIndex(index);
        unLink(node(index));
    }

    /**
     * @Author ysy
     * @Description 解除节点的链接
     * @Date 2022/1/10 13:16
     * @Param 
     * @return void
     **/
    private void unLink(Node<T> node) {
        Node<T> next = node.next;
        Node<T> prev = node.prev;
        // 处理prev节点：判断是否为头节点
        if(prev == null) {
            first = next;
        } else {
            prev.next = next;
            node.prev = null;
        }
        // 处理next节点：判断是否为尾节点
        if(next == null) {
            last = prev;
        } else {
            prev.prev = prev;
            node.next = null;
        }
        // 将值置为空
        node.data = null;
        size --;
    }

    /**
     * @Author ysy
     * @Description 删除指定对象
     * @Date 2022/1/10 12:46
     * @Param 
     * @return void
     **/
    public boolean remove(T data){
        // 若为null，则使用==比较
        if(data == null){
            // 遍历链表
            for (Node<T> node = first; node != null; node=node.next){
                if(node.data == null){
                    unLink(node);
                    return true;
                }
            }
        } else {
            // 若不为null，则使用equals比较
            for (Node<T> node = first; node != null; node=node.next){
                if(data.equals(node.data)){
                    unLink(node);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * @Author ysy
     * @Description 批量添加数据
     * @Date 2022/1/10 13:24
     * @Param
     * @return void
     **/
    public void addAll(Collection<? extends T> collection){
        addAll(size, collection);
    }

    /**
     * @Author ysy
     * @Description 从指定位置，批量添加数据
     * @Date 2022/1/10 12:44
     * @Param
     * @return void
     **/
    public void addAll(int index, Collection<? extends T> collection){
        checkIndex(index);
        Object[] array = collection.toArray();
        int arraySize = array.length;
        Node<T> preNode;
        Node<T> nextNode;
        // 初始化前后node
        if(index == size){
            // 若为尾插，则后node为null
            nextNode = null;
            preNode = last;
        } else {
            nextNode = node(index);
            preNode = nextNode.prev;
        }
        for(Object data : array){
            // 初始化新节点，指定前，不指定后
            Node<T> newNode = new Node<T>(preNode, (T)data, null);
            // 判断是否为头节点
            if(preNode == null){
                first = newNode;
            } else {
                preNode.next = newNode;
            }
            preNode = newNode;
        }
        // 若为尾插，指定last
        if(nextNode == null){
            last = preNode;
        } else {
            // 若不是尾插
            preNode.next = nextNode;
            nextNode.prev = preNode;
        }
        size += arraySize;
    }
}
